\documentclass[submission]{FPSAC2017}

\articlenumber{72}
\addbibresource{72_Smith.bib}

\usepackage{tikz}

\title{Pattern Posets}
\author{Jason P. Smith\thanks{This research was supported by the EPSRC Grant EP/M027147/1.}}

\address{Department of Computer and Information Sciences, University of Strathclyde, Glasgow, UK}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{rem}[thm]{Remark}
\newtheorem{conj}[thm]{Conjecture}
\numberwithin{equation}{section}
\numberwithin{thm}{section}

\DeclareMathOperator{\rk}{\textrm{rk}}
\DeclareMathOperator{\red}{\textrm{red}}
\DeclareMathOperator{\NE}{\textrm{NE}}

\received{\today}



\abstract{We introduce a formal definition of a pattern poset. This generalises many of the existing posets defined in terms of patterns on different combinatorial objects. We introduce a poset fibration on intervals of these posets. Applying this fibration gives some general results on pattern posets, that unify and generalise many of the existing results on these posets, such as Bj\"orner's results on subword order. We present a formula for the M\"obius function of intervals of pattern posets, which provides an explanation as to why the various definitions of normal embeddings play such an important role in many of the existing results for such posets. Moreover, we characterise when these posets are disconnected and show that Cohen-Macaulayness is preserved by our fibration. We also conjecture that fibrations preserve shellability under certain conditions. }

\keywords{Posets, Pattern Avoidance, Topology, Cohen-Macaulay, M\"obius Function}


\begin{document}
\maketitle
	

\section{Introduction}\label{sec:intro}

Pattern occurrence has been studied on a wide range of combinatorial objects with many different definitions of a pattern, see \cite{Kit11} for an overview of the field. In many of these cases we can use the notion of a pattern to define a poset on these objects, for example the classical permutation poset. Whilst many such pattern posets have been studied in isolation, there is no general framework for the study of these posets. Yet many of the known results follow a similar theme. By introducing a formal definition of a pattern poset, we present some general results on these posets that helps us to understand why different pattern posets often have a similar structure.

We say a word $\alpha$ occurs as a \emph{$\rho$-pattern} in a word $\beta$ if there is a subsequence of $\beta$ satisfying certain conditions $\rho$, and we  call this subsequence an \emph{occurrence of $\alpha$}. We can define a binary relation $\alpha\le_\rho\beta$ if $\alpha$ occurs as a $\rho$-pattern in $\beta$. If $\le_\rho$ satisfies the partial order conditions, then we can define a \emph{pattern poset} on a set of words. It is natural to ask questions on the structure and topology of a pattern poset $P$ and its \emph{intervals}, that is, the induced subposets $[\alpha,\beta]=\{\lambda\in P\,|\,\alpha\le\lambda\le~\beta\}$.
 
The topology of a poset is considered by mapping the poset to a simplicial complex, called the \emph{order complex}, whose faces are the chains of the poset, that is, the totally ordered subsets. We refer the reader to \cite{Wac07} for an overview of poset topology. A poset is \emph{shellable} if its maximal chains can be ordered in a certain way. Shellability implies a poset has many nice properties, such as Cohen-Macaulayness. We define a poset $P$ to be \emph{Cohen-Macaulay} if the order complex of $P$, and of every interval of $P$, is homotopically equivalent to a wedge of top dimensional spheres. The M\"obius function of a poset is defined recursively by $\mu(a,a)=1$ for all $a$, $\mu(a,b)=0$ if $a\not\le b$ and if $a<b$ then:
$$\mu(a,b)=-\sum_{a\le c< b}\mu(a,c).$$

The study of patterns in words has received a lot of attention. Perhaps the simplest type of pattern in a word is that of \emph{subword order}, that is, $u=u_1\ldots u_a$ occurs as a pattern in $w=w_1\ldots w_b$ if there is a subsequence $w_{i_1}\ldots w_{i_a}$ such that $w_{i_j}=u_j$ for all~$j=1,\ldots,a$. Bj\"orner \cite{Bjo90} presented a formula for the M\"obius function of the poset of words with subword order and showed that the poset is shellable. The poset of words with \emph{composition order} has the partial order $u\le w$ if there is a subsequence $w_{i_1}\ldots w_{i_a}$ such that $u_i\le w_{i_j}$ for all $j=1,\ldots,a$. A formula for the M\"obius function of this poset is given by Sagan and Vatter in~\cite{SagVat06}. Furthermore, the poset of generalised subword order is considered by McNamara and Sagan in~\cite{McnSag12} and Sagan and Vatter in~\cite{SagVat06}. There are many other examples of patterns in words and word representable objects, such as patterns in permutations, Dyck paths, set partitions, trees, ascent sequences and more.

Many of the known results on the M\"obius function of pattern posets, including those mentioned above, depend on the number of \emph{normal embeddings} defined in various but similar ways.  For example, they play an important role in the study of many different classes of intervals of the classical permutation poset, see \cite{BJJS11,McnSag12,SagVat06,Smith15,Smith14,Smith13}. We define an \emph{embedding} of $\alpha$ in $\beta$ as a sequence of dashes and the letters of $\alpha$, such that the positions of the non-dash letters give an occurrence of $\alpha$ in $\beta$ and deleting all the dashes results in $\alpha$. For example, $2-13-$ is an embedding of $213$ in $35142$. The definition of when an embedding is normal varies, but all follow a similar theme. Perhaps the simplest definition is that of Bj\"orner's for subword order \cite{Bjo90}, where the normal condition is that the only positions that can be dashes are the leftmost positions in the maximal consecutive sequences of equal letters.

We introduce a simple definition for normal embeddings which extracts the common theme from those in the literature. Using this definition we prove that the M\"obius function of a pattern poset, satisfying certain restrictions, equals the number of normal embeddings, plus an extra term that we describe explicitly. This extra term embodies the variations in the many definitions of normal embeddings. Furthermore, our general result can be used to prove many of the existing results on the M\"obius function of various pattern posets.

Poset fibrations are instrumental to our results. A fibration of a poset $Q$ consists of another poset $P$, called the total space, and a rank and order preserving surjective map~$f:P\rightarrow Q$. Poset fibrations were first studied by Quillen in \cite{Qui78} and a good overview is given in \cite{Bjo05}. We introduce a poset fibration on an interval $[\alpha,\beta]$ of a pattern poset. The total space of this fibration is built from the embeddings of $\lambda$ in $\beta$, for all~$\lambda\in(\alpha,\beta)$. This total space has a much nicer structure than the original poset, which allows us to compute the M\"obius function and topology of the total space. We can then use known results on poset fibrations to get results for the original interval. Moreover, we conjecture shellability is preserved across a poset fibration satisfying certain conditions, which would generalise a similar result for Cohen-Macaulayness.

It is known that a poset is not shellable if it contains a disconnected subinterval of rank greater than $2$. We say an interval is \emph{zero split} if its set of embeddings can be partitioned into two parts such that there is no position that appears as a dash in both. In~\cite{McSt13} it is shown that an interval of the classical permutation poset is disconnected if and only if it satisfies a slightly stronger condition than being zero split. We introduce a definition of \emph{strongly zero split} which generalises this result to pattern posets. This implies that if an interval contains a strongly zero split subinterval of rank greater than $2$, then it is not shellable. Furthermore, we show that an interval $[\alpha,\beta]$ is Cohen-Macaulay if the total space of $[\lambda,\beta]$ is Cohen-Macaulay, for all $\lambda\in[\alpha,\beta)$, and we conjecture a similar result exists for shellability.

In \cref{sec:patPos} we introduce a formal definition of pattern posets. In \cref{sec:posfib} we introduce a poset fibration on pattern posets. In \cref{sec:results} we prove some results on the  M\"obius function, disconnectedness and Cohen-Macaulayness of pattern posets. Finally, in \cref{sec:furth} we present some applications of these results.



\section{Pattern Posets}\label{sec:patPos}
The idea of \emph{pattern occurrence} has been used to consider a variety of different combinatorial objects. The notion of permutation pattern occurrence has received the most attention, but many others have also been considered. Pattern occurrence can be used to define a partial order and thus a poset. In this section we give a general definition of such a poset. First we need to formally define pattern occurrence. 

\begin{defn}\label{defn:patRel}
Given two words $\sigma,\pi$ on some alphabet $\Sigma$, we say that the subsequence\linebreak $\pi_{a_1}\ldots\pi_{a_k}$ is a \emph{$\rho$-occurrence} of~$\sigma$ in~$\pi$ if $\pi_{a_1}\ldots\pi_{a_k}\sim_\rho\sigma$, where $\sim_\rho$ is some binary relation we call a \emph{pattern relation}.
\end{defn}

\begin{ex}
Some examples of pattern relations are:

\begin{itemize}
\item Two words are related by $\sim_{\omega}$ if they are equal, which gives subword order, see \cite{Bjo90}.
\item Two words are related by $\sim_{\kappa}$ if their letters appear in the same relative order of size, which gives the classical permutation patterns, see \cite{McSt13}.
\item Given a poset $Q$, two words $\sigma$ and $\pi$ are related by $\sigma\sim_{\omega(Q)}\pi$ if $\sigma_i\le_Q\pi_i$ for all $i$, which gives generalised subword order, see \cite{McnSag12}.
\end{itemize}
\end{ex}

 In the same way that vincular patterns generalise the classical permutation pattern relation, we can generalise pattern relations to vincular pattern relations. To do this we use the notion of $A$-vincular permutation pattern posets introduced in \cite{BF14}. 

\begin{defn}
A \emph{vincular rule} is an infinite $(0,1)$-lower triangular matrix $M$. Given two words~$\sigma,\pi$ on the alphabet $\Sigma$ and a pattern relation $\sim_\rho$, we say there is a \emph{$(\rho,M)$-occurrence} of~$\sigma$ in $\pi$ if there is a subsequence $\pi_{a_1}\ldots\pi_{a_k}\sim_\rho\sigma$, where $a_{i+1}=a_i+1$ if $M_{i,k}=0$. We call the pair $(\rho,M)$ a \emph{vincular pattern relation}.
\end{defn}
\begin{ex}
If we let $M$ be the matrix with $1$'s in all positions on and below the diagonal, then we recover the pattern relation definition given in \cref{defn:patRel}. If we let $M$ be the matrix of all zeroes, then we require that any occurrence of $\sigma$ in $\pi$ must occur as a consecutive subsequence.
\end{ex}

We can use our notion of pattern relations to define a poset in following way:


\begin{defn}\label{defn:patPos}
Consider a vincular pattern relation $(\rho,M)$. Given $\sigma,\pi\in\Sigma^*$ we define a binary relation $\sigma\le_{(\rho,M)}\pi$ if there is a $(\rho,M)$-occurrence of $\sigma$ in~$\pi$. If $\le_{(\rho,M)}$ is reflexive, antisymmetric and transitive, then we define a \emph{pattern poset} $P(B,\rho,M)$ as the poset with elements $B\subseteq\Sigma^*$ and partial order $\le_{(\rho,M)}$.
\end{defn}
\begin{ex}\label{ex:PP}
Let $\mathcal{S}$ be the set of all permutations on the positive integers, $\mathcal{A}$ the set of all words on non-negative integers, $L_0$ the matrix of all zeroes and $L_1$ the matrix with all $1$'s on and below the diagonal.
\begin{itemize}
\item The poset $\mathbb{P}=P(\mathcal{S},\kappa,L_1)$ is the classical permutation pattern poset, see \cite{McSt13}.
\item The poset $\mathbb{W}=P(\mathcal{A},\omega,L_1)$ is the subword order poset, see \cite{Bjo90}.
\item The poset $P(\mathcal{S},\kappa,L_0)$ is the consecutive permutation pattern poset, see \cite{BFS11,EM15}.
\item If $B\subseteq\mathcal{A}$ is the set of Dyck words, then $P(B,\omega,L_1)$ is the Dyck pattern poset, see \cite{Bac14}.
\end{itemize}
\end{ex}
When the poset being considered is clear we drop the subscript and use the notation~$\le$.

\begin{defn}
We say a pattern poset $P$  is \emph{closed} if for every $\pi\in P$ and for every position $1\le i\le |\pi|$ there is a unique operation that changes only $\pi_i$ to create an element $\alpha\in P$ covered by $\pi$, we call this operation \emph{decreasing} position $i$. We say a pattern poset $P$ is an equivalence pattern poset if for every $\pi\in P$ every subword of $\pi$ is an occurrence of at most one element of $P$.
\end{defn}

For example, the decreasing operation on the permutation poset is deleting a letter and the decreasing operation on the poset of words with composition order is subtracting~$1$ from any letter $k>1$ or deleting a letter $k=1$. Here we give a list of known pattern posets and whether they are closed or equivalence posets, we omit the proof but the results are straightforward to verify in each case:
\begin{lem}\label{lem:PPex}
\begin{itemize}
\item The subword order poset and classical permutation poset are closed equivalence pattern posets.
\item The consecutive permutation poset and Dyck pattern poset are non-closed equivalence pattern poset.
\item The poset of words with composition order is a closed non-equivalence pattern poset
\end{itemize}
\end{lem}

Note that in a closed equivalence pattern poset every subword of every element is an occurrence of exactly one element of the pattern poset. Therefore, the decreasing operation is always deleting a letter. We use the notation equivalence because the equivalence condition implies the pattern relation is an equivalence relation. In the remainder of this abstract, for the sake of simplicity, we restrict our consideration to closed equivalence pattern posets. More general results can be found for posets that are non-closed or non-equivalence in \cite{Smith16}. 





\section{Poset Fibration}\label{sec:posfib}
In this section we introduce a poset fibration which we use to study pattern posets in \cref{sec:results}. A poset fibration is a rank and order preserving surjective map between posets. Poset fibrations where first studied by Quillen in \cite{Qui78} and have many nice properties. We can define a poset fibration using the embeddings of a pattern poset, where an embedding is defined as follows:

\begin{defn}
Consider a pattern poset $P$ and two elements $\alpha\le\beta$ of $P$. An \emph{embedding} of~$\alpha$ in~$\beta$ is a sequence of length $|\beta|$, consisting of the letters of $\alpha$ and dashes, such that the non-dash letters are exactly the positions of an occurrence of $\alpha$ in $\beta$ and removing the dashes results in~$\alpha$.

Let $E^{\alpha,\beta}$ be the set of embeddings of $\alpha$ in $\beta$. Given an embedding $\eta\in E^{\alpha,\beta}$, we call the positions of the dashed letters in $\eta$ the \emph{empty positions} and let the \emph{zero set} of $\eta$, denoted $Z(\eta)$, be the set of empty positions in~$\eta$.
\end{defn}
\begin{ex}
In $\mathbb{P}$ the sequence $-23--1$ is an embedding of $231$ in $156243$ and in $\mathbb{W}$ the sequence $-1-22-$ is an embedding of $122$ in $213221$.
\end{ex}

The notion of normal embeddings plays an important role in many of the existing results on the M\"obius function of pattern posets. For example, normal embeddings appear in results  on the poset of words with subword order \cite{Bjo93,Bjo90}, the poset of words with composition order \cite{SagVat06}, the poset of words with generalised subword order~\cite{McnSag12,SagVat06} and the classical permutation poset \cite{BJJS11,Smith15,Smith14,Smith13}. We generalise these notions of normal embeddings and present a simple definition for a normal embedding for any pattern poset. This definition is different from many definitions in the literature but extracts the common aspect of all of them, and the variation is then accounted for in our formula for the M\"obius function in \cref{sec:results}. First we introduce adjacencies, sometimes called runs, which play an important role in defining a normal embedding.

\begin{defn}
Consider a pattern poset $P:=P(B,\rho,A)$. An \emph{adjacency} in an element $\sigma\in P$ is a maximal sequence of consecutive positions such that removing any letter of the adjacency yields the same subword relative to $\sim_{(\rho,A)}$. An adjacency of length $1$ is \emph{trivial}, the \emph{tail} of a non-trivial adjacency is all but the first letter of the adjacency and trivial adjacencies have no tails.
\end{defn}
\begin{ex}
In $\mathbb{P}$ the permutation $2341657$ has adjacencies $234,\,1,\,65,\,7$ and the tails are~$34,\,5$. In $\mathbb{W}$ the word $21133322$ has adjacencies $2,11,333,22$ and tails $1,33,2$.
\end{ex}
\begin{defn}
Consider a pattern poset $P:=P(B,\rho,A)$ and two elements $\sigma,\pi\in P$. An embedding $\eta$ of $\sigma$ in $\pi$  is \emph{normal} if all the positions that are in a tail of any adjacency in $\pi$ are non-empty in $\eta$. Let $\NE(\sigma,\pi)$ denote the number of normal embeddings of $\sigma$ in $\pi$.

We call an embedding \emph{representative} if all non-empty positions have no empty positions to their right in the same adjacency.  Let $\hat{E}^{\sigma,\pi}$ be the set of representative embeddings of $\sigma$ in $\pi$.
\end{defn}
\begin{ex}
In $\mathbb{P}$ the embeddings of $213$ in $231645$ are:
$$2-13--\,\,\,\,\,\,\,\,-213--\,\,\,\,\,\,\,\,2-1-3-\,\,\,\,\,\,\,\,-21-3-\,\,\,\,\,\,\,\,2-1--3\,\,\,\,\,\,\,\,-21--3$$
The representative embeddings are $-213--$ and $-21--3$ and the only normal embedding is~$-21--3$.
\end{ex}

Note that a normal embedding is always representative. We can extend the partial order from our pattern poset to the embeddings, to get the following poset:

\begin{defn}\label{defn:PF}
Consider any interval $[\sigma,\pi]$ in a pattern poset $P$. Let $R(\sigma,\pi)$ be the poset of all representative embeddings of $\lambda$  in $\pi$, for all $\lambda\in(\sigma,\pi)$. The partial order of $R(\sigma,\pi)$ is given by $\eta\le\phi$ if $Z(\eta)\supseteq Z(\phi)$ and $\alpha\le_P\beta$, where $\alpha$ and $\beta$ are the words obtained by removing the empty positions from $\eta$ and $\phi$, respectively.

 Let $R^*(\sigma,\pi)$ be the poset of all representative embeddings of $\lambda$  in~$\pi$, for all $\lambda\in[\sigma,\pi)$. Let~$f^P_\pi:R(\sigma,\pi)\rightarrow (\sigma,\pi)$ map all elements of $\hat{E}^{\lambda,\pi}$ to $\lambda$, for all~$\lambda\in(\sigma,\pi)$. 
\end{defn}
\begin{ex}
Consider $\mathbb{P}$ then in the poset $R^*(1,243516)$ we have ${-213--\le-213-4}$\linebreak but ${-2--13\not\le-213-4}$. Consider $\mathbb{W}$ then in the poset $R^*(12,112221)$ we have\linebreak  ${-12--\le -1222-}$ but ${-12--\not\le --222-}$.
\end{ex}
\begin{rem}\label{rem:prodChains}
Let $\hat{R}(\sigma,\pi)$ be the poset obtained from $R(\sigma,\pi)$ by adding bottom and top elements~$\hat{0}$ and $\hat{1}$, respectively. Any interval $[\alpha,\beta]$ of $\hat{R}(\sigma,\pi)$, with $\alpha\not=\hat{0}$, is isomorphic to the Cartesian product of chains. To see this note that, each representative embedding $\eta$ can be represented as a sequence~$\hat{\eta}=\hat{\eta}_1\ldots\hat{\eta}_t$, where~$\hat{\eta}_i$ equals the number of non-empty positions that~$\eta$ embeds in the~$i$-th adjacency of $\pi$. If $\beta=\hat{1}$, let $\hat{\beta}_i$ be the length of the $i$-th adjacency in $\pi$. Then~$[\alpha,\beta]$ is isomorphic to $[\hat{\alpha}_1,\hat{\beta}_1]\times\cdots\times[\hat{\alpha}_t,\hat{\beta}_t]$. 
\end{rem}

We now have a poset fibration on $(\sigma,\pi)$, where $f^P_\pi$ is the projection map and $R(\sigma,\pi)$ is the total space. When it is clear we drop the subscripts and superscript and denote the fibration by $f$. In \cref{sec:results} we apply this poset fibration to prove some results on pattern posets. Note that we can also define a poset fibration where the total space is the poset of all embeddings, not just representative embeddings. We can apply the techniques we use in \cref{sec:results} to this fibration to get many interesting results as well, see \cite{Smith16}.


\section{Results on Pattern Posets}\label{sec:results}




\subsection{The M\"obius Function of Intervals of a Pattern Poset}
In this subsection we focus on the M\"obius function of pattern posets.  A poset is \emph{bounded} if it has a bottom and top element, which we denote $\hat{0}$ and $\hat{1}$, respectively. The \emph{M\"obius function} of a bounded poset $P$ is $\mu(P):=\mu(\hat{0},\hat{1})$. The \emph{M\"obius number} $\hat{\mu}(Q)$ of an unbounded poset $Q$ equals the M\"obius function of the poset obtained by adding a bottom and top element to $Q$. The following result, which is the dual of Corollary 3.2 in~\cite{Wal81}, proves very useful:
\begin{prop}\label{prop:wal81}
Given a poset fibration $f:P\rightarrow Q$:
$$\hat{\mu}(Q)=\hat{\mu}(P)+\sum_{q\in Q}\hat{\mu}(Q_{<q})\hat{\mu}(f^{-1}(Q_{\ge q})).$$
\end{prop}

We can use \cref{prop:wal81} along with our poset fibration to get the following result:

\begin{thm}\label{thm:muEta2}
If $[\sigma,\pi]$ is an interval of a pattern poset, then:
\begin{equation}\label{eq:main}\mu(\sigma,\pi)=(-1)^{|\pi|-|\sigma|}\NE(\sigma,\pi)+\sum_{\lambda\in[\sigma,\pi)}\mu(\sigma,\lambda)\hat{\mu}(R^*(\lambda,\pi)).\end{equation}
\begin{proof}
Applying \cref{prop:wal81} to the poset fibration given in \cref{defn:PF} gives:
\begin{equation}\label{eq:muA0}\mu(\sigma,\pi)=\hat{\mu}(R(\sigma,\pi))+\sum_{\lambda\in(\sigma,\pi)}\mu(\sigma,\lambda)\hat{\mu}(R^*(\lambda,\pi)).\end{equation}
The posets $R(\sigma,\pi)$ and $R^*(\sigma,\pi)$ can be considered as the union of the intervals~$(\eta,\hat{1})$ and $[\eta,\hat{1})$, respectively, for all $\eta\in\hat{E}^{\sigma,\pi}$. Applying an inclusion-exclusion argument for the M\"obius function we get:
\begin{equation}\label{eq:muA}\hat{\mu}(R(\sigma,\pi))=\sum_{\eta\in \hat{E}^{\sigma,\pi}}\mu(\eta,\hat{1})+\sum_{\substack{S\subseteq \hat{E}^{\sigma,\pi}\\|S|>1}}(-1)^{|S|}\hat{\mu}\left(\bigcap_{\eta\in S}(\eta,\hat{1})\right),\end{equation}
\begin{equation}\label{eq:muA3}\hat{\mu}(R^*(\sigma,\pi))=\sum_{\eta\in \hat{E}^{\sigma,\pi}}\hat{\mu}([\eta,\hat{1}))+\sum_{\substack{S\subseteq \hat{E}^{\sigma,\pi}\\|S|>1}}(-1)^{|S|}\hat{\mu}\left(\bigcap_{\eta\in S}(\eta,\hat{1})\right).\end{equation}

Note that in~\eqref{eq:muA3} we use the intersections of $(\eta,\hat{1})$ instead of $[\eta,\hat{1})$, because these are equivalent as $\eta$ will never be in the intersections. Moreover, $\hat{\mu}([\eta,\hat{1}))$ has the unique bottom element $\eta$, thus the M\"obius number equals $0$. So the first term on the right hand side of~\eqref{eq:muA3} equals zero. Therefore, the second term on the right hand side of~\eqref{eq:muA} is equal to $\hat{\mu}(R^*(\sigma,\pi))$, so we have:
\begin{equation}\label{eq:muA2}\hat{\mu}(R(\sigma,\pi))=\sum_{\eta\in \hat{E}^{\sigma,\pi}}\mu(\eta,\hat{1})+\hat{\mu}(R^*(\sigma,\pi)).\end{equation}
Combining~\eqref{eq:muA0} and~\eqref{eq:muA2} implies that:
\begin{equation}\label{eq:muA4}\mu(\sigma,\pi)=\sum_{\eta\in \hat{E}^{\sigma,\pi}}\mu(\eta,\hat{1})+\sum_{\lambda\in[\sigma,\pi)}\mu(\sigma,\lambda)\hat{\mu}(R^*(\lambda,\pi)).\end{equation}

Finally, by \cref{rem:prodChains} we know that $[\eta,\hat{1}]$ is the Cartesian product of chains, for any~$\eta\in\hat{E}^{\sigma,\pi}$. Moreover, these chains all have length at most $1$ if and only if $\eta$ is normal. If $\eta$ is normal then there are $|\pi|-|\sigma|$ chains of length $1$, the rest having length~$0$. The M\"obius function of a chain is $1$ if the chain has length $0$, $-1$ if the chain has length~$1$ and $0$ otherwise. Furthermore, the M\"obius function of the Cartesian product of posets is the product of the M\"obius functions. Therefore, $\mu(\eta,\hat{1})$ equals~$(-1)^{|\pi|-|\sigma|}$ if~$\eta$ is normal and $0$ otherwise. So the first term on the right hand side of~\eqref{eq:muA4} equals~$(-1)^{|\pi|-|\sigma|}\NE(\sigma,\pi)$, which completes the proof.
\end{proof}
\end{thm}


\cref{thm:muEta2} provides an explanation as to why normal embeddings play such an important role in many of the existing results on the M\"obius function of pattern posets.  The second term on the right hand side of~\eqref{eq:main} is what leads to the variations in the definitions of normal in these cases. Furthermore, we can apply \cref{thm:muEta2} to provide an alternative proof to some of these existing results. For example, we can prove the formula for the M\"obius function of words with subword order given in \cite{Bjo90}. To do this we show that $\hat{\mu}(R^*(u,w))=0$ for any interval $[u,w]$ of the poset of words with subword order, which implies $\mu(u,w)=(-1)^{|w|-|u|}\NE(u,w)$.



\subsection{Disconnected Intervals of a Pattern Poset}
In this section we study the property of disconnectedness in pattern posets. A bounded poset is \emph{disconnected} if the interior can be split into two disjoint sets, which we call \emph{components}, such that any pair of elements from separate components are incomparable. Proposition 5.3 of \cite{McSt13} gives a characterisation of when an interval of the classical permutation poset is disconnected, based on whether the set of embeddings can be split in a certain way. In this subsection we generalise this result to all pattern posets.

\begin{defn}
An interval $[\sigma,\pi]$, with $\rk(\sigma,\pi)\ge 2$, is \emph{zero split}  if the  representative embedding set can be partitioned into two disjoint non-empty sets $E_1$ and $E_2$ such that $Z(E_1)\cap Z(E_2)=\emptyset$, where $Z(E_i)$ is the union of the zero sets of the elements of $E_i$.

 We say that $[\sigma,\pi]$ is \emph{strongly zero split} if there exists a zero split partition $E_1$ and $E_2$ of~$\hat{E}^{\sigma,\pi}$ which satisfies the following condition: For all $\eta_1\in E_1$ and $\eta_2\in E_2$ there does not exist a pair~$z_1\in Z(\eta_1)$ and $z_2\in Z(\eta_2)$ such that the embeddings in $\pi$ with zero sets $Z(\eta_1)\setminus\{z_1\}$ and $Z(\eta_2)\setminus\{z_2\}$ are embeddings of the same element $\lambda$ in $\pi$.
\end{defn}
\begin{ex}
Consider the interval $[41253,41627385]$ of $\mathbb{P}$. The representative embeddings are $\eta_1=41-253--$ and $\eta_2=--41-253$. If we partition the representative embeddings into the sets $E_1=\{\eta_1\}$ and $E_2=\{\eta_2\}$, then this is a zero split partition but not a strongly zero split partition. To see this is not a strongly zero split partition, note that $Z(\eta_1)=\{3,7,8\}$ and $Z(\eta_2)=\{1,2,5\}$. The embeddings with zero sets $Z(\eta_1)\setminus\{3\}$ and $Z(\eta_2)\setminus\{5\}$ are $415263--$ and $--415263$, respectively, which are both embeddings of~$415263$. Therefore, the condition for a strongly zero split partition is violated.
\end{ex}


Our definition of strongly zero split generalises the conditions given in \cite{McSt13}. Note that the conditions given in \cite{McSt13} are defined on the set of all embeddings and we only consider the representative embeddings. However, we can also define strongly zero split on the set of all embeddings, and it can be shown that the embedding set is strongly zero split  if and only if the representative embedding is strongly zero split. Therefore, our definition of strongly zero split is a generalisation to all pattern posets of the conditions given in~\cite{McSt13}.

Note that the join of any two embeddings $\alpha,\beta\in R^*(\sigma,\pi)$ is given by the embedding with the zero set~$Z(\alpha)\cap Z(\beta)$. We can use this to show that an interval $[\sigma,\pi]$ being zero split is intrinsically related to the connectedness of the posets $R(\sigma,\pi)$, $R^*(\sigma,\pi)$ and~$[\sigma,\pi]$. 

\begin{lem}\label{lem:discon}
An interval $[\sigma,\pi]$ of a pattern poset, with $\rk(\sigma,\pi)\ge 2$, is zero split if and only if $R^*(\sigma,\pi)$ is disconnected. Furthermore, if $\rk(\sigma,\pi)\ge3$, then~$[\sigma,\pi]$ is zero split if and only if~$R(\sigma,\pi)$ is disconnected.
\begin{proof}
We consider the poset $R^*(\sigma,\pi)$, the argument is similar for $R(\sigma,\pi)$. First suppose that $[\sigma,\pi]$ is zero split with the partition $E_1$ and $E_2$ of $\hat{E}^{\sigma,\pi}$. Let $P_1$ and $P_2$ be the elements of $R^*(\sigma,\pi)$ that contain an element of $E_1$ and $E_2$, respectively. Note that any two atoms~$\eta_1\in E_1$ and $\eta_2\in E_2$ have $Z(\eta_1)\cap Z(\eta_2)=\emptyset$, so their join is $\hat{1}$. Therefore,  $P_1$ and~$P_2$ are disconnected components of $R^*(\sigma,\pi)$.

Now suppose $R^*(\sigma,\pi)$ is disconnected with components $P_1$ and $P_2$, which have atoms~$E_1$ and~$E_2$, respectively. The join of any elements $\eta_1\in E_1$ and $\eta_2\in E_2$  equals~$\hat{1}$ which implies that the intersection of their zero set is empty. Moreover, because this is true for any pair, it implies $E_1$ and $E_2$ form a zero split partition of $\hat{E}^{\sigma,\pi}$.
\end{proof}
\end{lem}

\begin{prop}\label{prop:discon}
An interval $[\sigma,\pi]$ of a pattern poset, with $\rk(\sigma,\pi)\ge3$, is disconnected if and only if $[\sigma,\pi]$ is strongly zero split.
\begin{proof}
First suppose that $[\sigma,\pi]$ is strongly zero split with the zero split partition $E_1$ and~$E_2$. Then $R(\sigma,\pi)$ is disconnected by \cref{lem:discon}. So the only way that $[\sigma,\pi]$ is not disconnected is if there are two embeddings $\kappa_1$ and $\kappa_2$ in separate components of~$R(\sigma,\pi)$ such that $f(\kappa_1)=f(\kappa_2)$, where $f$ is the poset fibration map. First note that if $f(\kappa_1)=f(\kappa_2)$, then for any $\phi_1\le\kappa_1$ there exists is a $\phi_2\le\kappa_2$ such that $f(\phi_1)=f(\phi_2)$. Therefore, we need only consider the case that $\kappa_1$ and $\kappa_2$ are atoms.

 So suppose $\kappa_1$ and $\kappa_2$ are atoms with zero sets $Z(\kappa_i)=Z(\eta_i)\setminus\{z_i\}$, where $\eta_i\in E_i$ and~$z_i\in Z(\eta_i)$, for $i=1,2$. However, this implies that the embeddings with zero sets~$Z(\eta_1)\setminus\{z_1\}$ and $Z(\eta_2)\setminus\{z_2\}$ are embeddings of the same element $f(\kappa_1)$ in $\pi$, which is exactly the forbidden situation in the definition of strongly zero split. Therefore, we cannot have elements from separate components mapping to the same element, so~$[\sigma,\pi]$ is disconnected. The other direction follows by a similar argument in reverse.
\end{proof}
\end{prop}

Applying \cref{prop:discon} to the permutation poset implies Proposition~5.3 of~\cite{McSt13}. 


\subsection{Cohen-Macaulayness of Intervals of a Pattern Poset}\label{sec:shellPres}
We define a poset to be \emph{Cohen-Macaulay} if the order complex of the poset, and of every interval of the poset, is homotopically equivalent to a wedge of top dimensional spheres. Theorem~5.2 of~\cite{Bjo05} shows that Cohen-Macaulayness is preserved by a poset fibration satisfying certain conditions. We present a slightly altered form of this result as \cref{prop:fibCM} below, a proof of which can be found in \cite{Smith16}.

 First we recall some notation. A poset is \emph{pure} if all maximal chains are the same length. Note that a closed pattern poset is always pure. Given a poset $P$ and an element~$p\in P$ define the induced subposet $P_{<p}=\{q\in P\,|\,q<p\}$ and similarly define~$P_{\le p}$,~$P_{>p}$ and~$P_{\ge p}$.
\begin{prop}\label{prop:fibCM}
Let $P$ and $Q$ be pure posets and let $f:P\rightarrow Q$ be a poset fibration. Assume that for all $q\in Q$  there is some $p_q\in P$ such that $Q_{<q}=f(P_{<p_q})$ and $f^{-1}(Q_{\ge q})$ is Cohen-Macaulay. If $P$ is Cohen-Macaulay, then $Q$ is Cohen-Macaulay.
\end{prop}

We can use \cref{prop:fibCM} to get the following results on pattern posets:
\begin{thm}\label{thm:PPCM}
Consider an interval $[\sigma,\pi]$ of a pattern poset $P$ such that $R^*(\lambda,\pi)$ is Cohen-Macaulay for all $\lambda\in(\sigma,\pi)$. If $R(\sigma,\pi)$ is Cohen-Macaulay, then $[\sigma,\pi]$ is Cohen-Macaulay.
\begin{proof}
It is straightforward to see that any  embedding of $\lambda$ in $\pi$ contains an embedding of $\omega$ in $\pi$, for all $\omega\in(\sigma,\lambda)$. Therefore, $(\sigma,\pi)_{<\lambda}=f(R(\sigma,\pi)_{<\psi})$, for any $\psi\in\hat{E}^{\lambda,\pi}$. Furthermore, $f^{-1}((\sigma,\pi)_{\ge\lambda})=f^{-1}([\lambda,\pi))=R^*(\lambda,\pi)$ which is CL-shellable by assumption, for any $\lambda\in [\sigma,\pi)$. So the result follows by \cref{prop:fibCM}.
\end{proof}
\end{thm}

A Cohen-Macaulay poset cannot contain a disconnected subposet of rank greater than $2$. Therefore, \cref{prop:discon} implies the following result:

\begin{cor}
If $[\sigma,\pi]$ is an interval of a pattern poset and contains a strongly zero split subinterval of rank greater than $2$, then $[\sigma,\pi]$ is not Cohen-Macaulay, thus not shellable.
\end{cor}

We believe that \cref{prop:fibCM}, and similarly Theorems 5.1(i) and 5.2 of \cite{Bjo05}, can be generalised to show that shellability is also preserved across a poset fibration.
\begin{conj}\label{conj:fibShell}
Let $P$ and $Q$ be pure posets and let $f:P\rightarrow Q$ be a poset fibration. Assume that for all $q\in Q$  there is some $p_q\in P$ such that $Q_{<q}=f(P_{<p_q})$ and $f^{-1}(Q_{\ge q})$ is shellable. If~$P$ is shellable, then $Q$ is shellable.
\end{conj}

Then the following result would follow immediately:

\begin{conj}\label{conj:PPshell2}
Consider an interval $[\sigma,\pi]$ of a pattern poset such that $R^*(\lambda,\pi)$ is shellable for all  $\lambda\in(\sigma,\pi)$. If $R(\sigma,\pi)$ is shellable, then $[\sigma,\pi]$ is shellable.
\end{conj}



\section{Applications}\label{sec:furth}

We can apply the results from \cref{sec:results} to many different pattern posets. This enables us to provide alternative proofs of existing results and discover new results. For example, it can easily be shown that if $[u,w]$ is an interval of the poset of words with subword order, then $R(u,w)$ and $R^*(u,w)$ are shellable and $\hat{\mu}(R^*(u,w))=0$. This gives an alternative proof of Bj\"orner's results in~\cite{Bjo90}, that intervals of the poset of words with subword order are Cohen-Macaulay and their M\"obius function equals the number of normal embeddings.


\printbibliography

\end{document}